1//////////////////////////////////////////////////////////////////////
2// LibFile: lists.scad
3// Functions for operating on generic lists. Provides functiosn for indexing lists, changing list
4// structure, and constructing lists by rearranging or modifying another list.
5// Includes:
6// include <BOSL2/std.scad>
7// FileGroup: Data Management
8// FileSummary: List indexing, change list structure, rearrange/modify lists
9// FileFootnotes: STD=Included in std.scad
10//////////////////////////////////////////////////////////////////////
11
12// Terminology:
13// **List** = An ordered collection of zero or more arbitrary items. ie: `["a", "b", "c"]`, or `[3, "a", [4,5]]`
14// **Vector** = A list of numbers. ie: `[4, 5, 6]`
15// **Set** = A list of unique items.
16
17// Section: List Query Operations
18
19// Function: is_homogeneous()
20// Alias: is_homogenous()
21// Synopsis: Returns true if all members of a list are of the same type.
22// Topics: List Handling, Type Checking
23// See Also: is_vector(), is_matrix()
24// Usage:
25// bool = is_homogeneous(list, [depth]);
26// Description:
27// Returns true when the list has elements of same type up to the depth `depth`.
28// Booleans and numbers are not distinguinshed as of distinct types.
29// Arguments:
30// l = the list to check
31// depth = the lowest level the check is done. Default: 10
32// Example:
33// a = is_homogeneous([[1,["a"]], [2,["b"]]]); // Returns true
34// b = is_homogeneous([[1,["a"]], [2,[true]]]); // Returns false
35// c = is_homogeneous([[1,["a"]], [2,[true]]], 1); // Returns true
36// d = is_homogeneous([[1,["a"]], [2,[true]]], 2); // Returns false
37// e = is_homogeneous([[1,["a"]], [true,["b"]]]); // Returns true
38function is_homogeneous(l, depth=10) =
39 !is_list(l) || l==[] ? false :
40 let( l0=l[0] )
41 [] == [for(i=[1:1:len(l)-1]) if( ! _same_type(l[i],l0, depth+1) ) 0 ];
42
43function is_homogenous(l, depth=10) = is_homogeneous(l, depth);
44
45
46function _same_type(a,b, depth) =
47 (depth==0) ||
48 (is_undef(a) && is_undef(b)) ||
49 (is_bool(a) && is_bool(b)) ||
50 (is_num(a) && is_num(b)) ||
51 (is_string(a) && is_string(b)) ||
52 (is_list(a) && is_list(b) && len(a)==len(b)
53 && []==[for(i=idx(a)) if( ! _same_type(a[i],b[i],depth-1) ) 0] );
54
55
56// Function: min_length()
57// Synopsis: Given a list of sublists, returns the length of the shortest sublist.
58// Topics: List Handling
59// See Also: max_length()
60// Usage:
61// llen = min_length(list);
62// Description:
63// Returns the length of the shortest sublist in a list of lists.
64// Arguments:
65// list = A list of lists.
66// Example:
67// slen = min_length([[3,4,5],[6,7,8,9]]); // Returns: 3
68function min_length(list) =
69 assert(is_list(list), "Invalid input." )
70 min([for (v = list) len(v)]);
71
72
73// Function: max_length()
74// Synopsis: Given a list of sublists, returns the length of the longest sublist.
75// Topics: List Handling
76// See Also: min_length()
77// Usage:
78// llen = max_length(list);
79// Description:
80// Returns the length of the longest sublist in a list of lists.
81// Arguments:
82// list = A list of lists.
83// Example:
84// llen = max_length([[3,4,5],[6,7,8,9]]); // Returns: 4
85function max_length(list) =
86 assert(is_list(list), "Invalid input." )
87 max([for (v = list) len(v)]);
88
89
90
91
92// Internal. Not exposed.
93function _list_shape_recurse(v) =
94 !is_list(v[0])
95 ? len( [for(entry=v) if(!is_list(entry)) 0] ) == 0 ? [] : [undef]
96 : let(
97 firstlen = is_list(v[0]) ? len(v[0]): undef,
98 first = len( [for(entry = v) if(! is_list(entry) || (len(entry) != firstlen)) 0 ] ) == 0 ? firstlen : undef,
99 leveldown = flatten(v)
100 )
101 is_list(leveldown[0])
102 ? concat([first],_list_shape_recurse(leveldown))
103 : [first];
104
105function _list_shape_recurse(v) =
106 let( alen = [for(vi=v) is_list(vi) ? len(vi): -1] )
107 v==[] || max(alen)==-1 ? [] :
108 let( add = max(alen)!=min(alen) ? undef : alen[0] )
109 concat( add, _list_shape_recurse(flatten(v)));
110
111
112// Function: list_shape()
113// Synopsis: Returns the dimensions of an array.
114// Topics: Matrices, List Handling
115// See Also: is_homogenous()
116// Usage:
117// dims = list_shape(v, [depth]);
118// Description:
119// Returns the size of a multi-dimensional array, a list of the lengths at each depth.
120// If the returned value has `dims[i] = j` then it means the ith index ranges of j items.
121// The return `dims[0]` is equal to the length of v. Then `dims[1]` is equal to the
122// length of the lists in v, and in general, `dims[i]` is equal to the length of the items
123// nested to depth i in the list v. If the length of items at that depth is inconsistent, then
124// `undef` is returned. If no items exist at that depth then `0` is returned. Note that
125// for simple vectors or matrices it is faster to compute `len(v)` and `len(v[0])`.
126// Arguments:
127// v = list to get shape of
128// depth = depth to compute the size of. If not given, returns a list of sizes at all depths.
129// Example:
130// a = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]]); // Returns [2,2,3]
131// b = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]], 0); // Returns 2
132// c = list_shape([[[1,2,3],[4,5,6]],[[7,8,9],[10,11,12]]], 2); // Returns 3
133// d = list_shape([[[1,2,3],[4,5,6]],[[7,8,9]]]); // Returns [2,undef,3]
134function list_shape(v, depth=undef) =
135 assert( is_undef(depth) || ( is_finite(depth) && depth>=0 ), "Invalid depth.")
136 ! is_list(v) ? 0 :
137 (depth == undef)
138 ? concat([len(v)], _list_shape_recurse(v))
139 : (depth == 0)
140 ? len(v)
141 : let( dimlist = _list_shape_recurse(v))
142 (depth > len(dimlist))? 0 : dimlist[depth-1] ;
143
144
145
146// Function: in_list()
147// Synopsis: Returns true if a value is in a list.
148// Topics: List Handling
149// See Also: select(), slice()
150// Usage:
151// bool = in_list(val, list, [idx]);
152// Description:
153// Returns true if value `val` is in list `list`. When `val==NAN` the answer will be false for any list.
154// Arguments:
155// val = The simple value to search for.
156// list = The list to search.
157// idx = If given, searches the given columns for matches for `val`.
158// Example:
159// a = in_list("bar", ["foo", "bar", "baz"]); // Returns true.
160// b = in_list("bee", ["foo", "bar", "baz"]); // Returns false.
161// c = in_list("bar", [[2,"foo"], [4,"bar"], [3,"baz"]], idx=1); // Returns true.
162
163// Note that a huge complication occurs because OpenSCAD's search() finds
164// index i as a hits if the val equals list[i] but also if val equals list[i][0].
165// This means every hit needs to be checked to see if it's actually a hit,
166// and if the first hit is a mismatch we have to keep searching.
167// We assume that the normal case doesn't have mixed data, and try first
168// with just one hit, but if this finds a mismatch then we try again
169// with all hits, which could be slow for long lists.
170function in_list(val,list,idx) =
171 assert(is_list(list),"Input is not a list")
172 assert(is_undef(idx) || is_finite(idx), "Invalid idx value.")
173 let( firsthit = search([val], list, num_returns_per_match=1, index_col_num=idx)[0] )
174 firsthit==[] ? false
175 : is_undef(idx) && val==list[firsthit] ? true
176 : is_def(idx) && val==list[firsthit][idx] ? true
177 // first hit was found but didn't match, so try again with all hits
178 : let ( allhits = search([val], list, 0, idx)[0])
179 is_undef(idx) ? [for(hit=allhits) if (list[hit]==val) 1] != []
180 : [for(hit=allhits) if (list[hit][idx]==val) 1] != [];
181
182
183
184// Section: List Indexing
185
186// Function: select()
187// Synopsis: Returns one or more items from a list, with wrapping.
188// Topics: List Handling
189// See Also: slice(), column(), last()
190// Description:
191// Returns a portion of a list, wrapping around past the beginning, if end<start.
192// The first item is index 0. Negative indexes are counted back from the end.
193// The last item is -1. If only the `start` index is given, returns just the value
194// at that position when `start` is a number or the selected list of entries when `start` is
195// a list of indices or a range.
196// Usage:
197// item = select(list, start);
198// item = select(list, [s:d:e]);
199// item = select(list, [i0,i1...,ik]);
200// list = select(list, start, end);
201// Arguments:
202// list = The list to get the portion of.
203// start = Either the index of the first item or an index range or a list of indices.
204// end = The index of the last item when `start` is a number. When `start` is a list or a range, `end` should not be given.
205// Example:
206// l = [3,4,5,6,7,8,9];
207// a = select(l, 5, 6); // Returns [8,9]
208// b = select(l, 5, 8); // Returns [8,9,3,4]
209// c = select(l, 5, 2); // Returns [8,9,3,4,5]
210// d = select(l, -3, -1); // Returns [7,8,9]
211// e = select(l, 3, 3); // Returns [6]
212// f = select(l, 4); // Returns 7
213// g = select(l, -2); // Returns 8
214// h = select(l, [1:3]); // Returns [4,5,6]
215// i = select(l, [3,1]); // Returns [6,4]
216function select(list, start, end) =
217 assert( is_list(list) || is_string(list), "Invalid list.")
218 let(l=len(list))
219 l==0
220 ? []
221 : end==undef
222 ? is_num(start)
223 ? list[ (start%l+l)%l ]
224 : assert( start==[] || is_vector(start) || is_range(start), "Invalid start parameter")
225 [for (i=start) list[ (i%l+l)%l ] ]
226 : assert(is_finite(start), "When `end` is given, `start` parameter should be a number.")
227 assert(is_finite(end), "Invalid end parameter.")
228 let( s = (start%l+l)%l, e = (end%l+l)%l )
229 (s <= e)
230 ? [ for (i = [s:1:e]) list[i] ]
231 : [ for (i = [s:1:l-1]) list[i],
232 for (i = [0:1:e]) list[i] ] ;
233
234
235// Function: slice()
236// Synopsis: Returns part of a list without wrapping.
237// Topics: List Handling
238// See Also: select(), column(), last()
239// Usage:
240// list = slice(list, s, e);
241// Description:
242// Returns a slice of a list, from the first position `s` up to and including the last position `e`.
243// The first item in the list is at index 0. Negative indexes are counted back from the end, with
244// -1 referring to the last list item. If `s` is after `e` then the empty list is returned.
245// If an index is off the start/end of the list it will refer to the list start/end.
246// Arguments:
247// list = The list to get the slice of.
248// start = The index of the first item to return. Default: 0
249// end = The index of the last item to return. Default: -1 (last item)
250// Example:
251// a = slice([3,4,5,6,7,8,9], 3, 5); // Returns [6,7,8]
252// b = slice([3,4,5,6,7,8,9], 2, -1); // Returns [5,6,7,8,9]
253// c = slice([3,4,5,6,7,8,9], 1, 1); // Returns [4]
254// d = slice([3,4,5,6,7,8,9], 5); // Returns [8,9]
255// e = slice([3,4,5,6,7,8,9], 2, -2); // Returns [5,6,7,8]
256// f = slice([3,4,5,6,7,8,9], 4, 3; // Returns []
257// g = slice([3,4,5], 1, 5; // Returns [4,5]
258// h = slice([3,4,5], 5, 7); // Returns []
259function slice(list,start=0,end=-1) =
260 assert(is_list(list))
261 assert(is_int(start))
262 assert(is_int(end))
263 !list? [] :
264 let(
265 l = len(list),
266 start = start+(start<0 ? l : 0),
267 end = end + (end<0? l : 0)
268 )
269 [if (start<=end && end>=0 && start<=l) for (i=[max(start,0):1:min(end,l-1)]) list[i]];
270
271
272// Function: last()
273// Synopsis: Returns the last item of a list.
274// Topics: List Handling
275// See Also: select(), slice(), column()
276// Usage:
277// item = last(list);
278// Description:
279// Returns the last element of a list, or undef if empty.
280// Arguments:
281// list = The list to get the last element of.
282// Example:
283// l = [3,4,5,6,7,8,9];
284// x = last(l); // Returns 9.
285function last(list) =
286 list[len(list)-1];
287
288
289// Function: list_head()
290// Synopsis: Returns the elements at the beginning of a list.
291// Topics: List Handling
292// See Also: select(), slice(), list_tail(), last()
293// Usage:
294// list = list_head(list, [to]);
295// Description:
296// Returns the head of the given list, from the first item up until the `to` index, inclusive.
297// By default returns all but the last element of the list.
298// If the `to` index is negative, then the length of the list is added to it, such that
299// `-1` is the last list item. `-2` is the second from last. `-3` is third from last, etc.
300// If the list is shorter than the given index, then the full list is returned.
301// Arguments:
302// list = The list to get the head of.
303// to = The last index to include. If negative, adds the list length to it. ie: -1 is the last list item. Default: -2
304// Example:
305// hlist1 = list_head(["foo", "bar", "baz"]); // Returns: ["foo", "bar"]
306// hlist2 = list_head(["foo", "bar", "baz"], -3); // Returns: ["foo"]
307// hlist3 = list_head(["foo", "bar", "baz"], 2); // Returns: ["foo","bar"]
308// hlist4 = list_head(["foo", "bar", "baz"], -5); // Returns: []
309// hlist5 = list_head(["foo", "bar", "baz"], 5); // Returns: ["foo","bar","baz"]
310function list_head(list, to=-2) =
311 assert(is_list(list))
312 assert(is_finite(to))
313 to<0? [for (i=[0:1:len(list)+to]) list[i]] :
314 to<len(list)? [for (i=[0:1:to]) list[i]] :
315 list;
316
317
318// Function: list_tail()
319// Synopsis: Returns the elements at the end of a list.
320// Topics: List Handling
321// See Also: select(), slice(), list_tail(), last()
322// Usage:
323// list = list_tail(list, [from]);
324// Description:
325// Returns the tail of the given list, from the `from` index up until the end of the list, inclusive.
326// By default returns all but the first item.
327// If the `from` index is negative, then the length of the list is added to it, such that
328// `-1` is the last list item. `-2` is the second from last. `-3` is third from last, etc.
329// If you want it to return the last three items of the list, use `from=-3`.
330// Arguments:
331// list = The list to get the tail of.
332// from = The first index to include. If negative, adds the list length to it. ie: -1 is the last list item. Default: 1.
333// Example:
334// tlist1 = list_tail(["foo", "bar", "baz"]); // Returns: ["bar", "baz"]
335// tlist2 = list_tail(["foo", "bar", "baz"], -1); // Returns: ["baz"]
336// tlist3 = list_tail(["foo", "bar", "baz"], 2); // Returns: ["baz"]
337// tlist4 = list_tail(["foo", "bar", "baz"], -5); // Returns: ["foo","bar","baz"]
338// tlist5 = list_tail(["foo", "bar", "baz"], 5); // Returns: []
339function list_tail(list, from=1) =
340 assert(is_list(list))
341 assert(is_finite(from))
342 from>=0? [for (i=[from:1:len(list)-1]) list[i]] :
343 let(from = from + len(list))
344 from>=0? [for (i=[from:1:len(list)-1]) list[i]] :
345 list;
346
347
348
349// Function: bselect()
350// Synopsis: Select list items using boolean index list.
351// Topics: List Handling
352// See Also: list_bset()
353// Usage:
354// sublist = bselect(list, index);
355// Description:
356// Returns the items in `list` whose matching element in `index` evaluates as true.
357// Arguments:
358// list = Initial list (or string) to extract items from.
359// index = List of values that will be evaluated as boolean, same length as `list`.
360// Example:
361// a = bselect([3,4,5,6,7], [false,true,true,false,true]); // Returns: [4,5,7]
362function bselect(list,index) =
363 assert(is_list(list)||is_string(list), "First argument must be a list or string." )
364 assert(is_list(index) && len(index)==len(list) , "Second argument must have same length as the first." )
365 is_string(list)? str_join(bselect( [for (x=list) x], index)) :
366 [for(i=idx(list)) if (index[i]) list[i]];
367
368
369// Section: List Construction
370
371
372// Function: repeat()
373// Synopsis: Returns a list of repeated copies of a value.
374// Topics: List Handling
375// See Also: count(), lerpn()
376// Usage:
377// list = repeat(val, n);
378// Description:
379// Generates a list of `n` copies of the given value `val`.
380// If the count `n` is given as a list of counts, then this creates a
381// multi-dimensional array, filled with `val`. If `n` is negative, returns the empty list.
382// Arguments:
383// val = The value to repeat to make the list or array.
384// n = The number of copies to make of `val`. Can be a list to make an array of copies.
385// Example:
386// a = repeat(1, 4); // Returns [1,1,1,1]
387// b = repeat(8, [2,3]); // Returns [[8,8,8], [8,8,8]]
388// c = repeat(0, [2,2,3]); // Returns [[[0,0,0],[0,0,0]], [[0,0,0],[0,0,0]]]
389// d = repeat([1,2,3],3); // Returns [[1,2,3], [1,2,3], [1,2,3]]
390// e = repeat(4, -1); // Returns []
391function repeat(val, n, i=0) =
392 is_num(n)? [for(j=[1:1:n]) val] :
393 assert( is_list(n), "Invalid count number.")
394 (i>=len(n))? val :
395 [for (j=[1:1:n[i]]) repeat(val, n, i+1)];
396
397
398
399// Function: list_bset()
400// Synopsis: Returns a list where values are spread to locations indicated by a boolean index list.
401// Topics: List Handling
402// See Also: bselect()
403// Usage:
404// arr = list_bset(indexset, valuelist, [dflt]);
405// Description:
406// Opposite of `bselect()`. Returns a list the same length as `indexlist`, where each item will
407// either be 0 if the corresponding item in `indexset` is false, or the next sequential value
408// from `valuelist` if the item is true. The number of `true` values in `indexset` must be equal
409// to the length of `valuelist`.
410// Arguments:
411// indexset = A list of boolean values.
412// valuelist = The list of values to set into the returned list.
413// dflt = Default value to store when the indexset item is false. Default: 0
414// Example:
415// a = list_bset([false,true,false,true,false], [3,4]); // Returns: [0,3,0,4,0]
416// b = list_bset([false,true,false,true,false], [3,4], dflt=1); // Returns: [1,3,1,4,1]
417function list_bset(indexset, valuelist, dflt=0) =
418 assert(is_list(indexset), "The index set is not a list." )
419 assert(is_list(valuelist), "The `valuelist` is not a list." )
420 let( trueind = search([true], indexset,0)[0] )
421 assert( !(len(trueind)>len(valuelist)), str("List `valuelist` too short; its length should be ",len(trueind)) )
422 assert( !(len(trueind)<len(valuelist)), str("List `valuelist` too long; its length should be ",len(trueind)) )
423 concat(
424 list_set([],trueind, valuelist, dflt=dflt), // Fill in all of the values
425 repeat(dflt,len(indexset)-max(trueind)-1) // Add trailing values so length matches indexset
426 );
427
428
429
430// Function: list()
431// Synopsis: Expands a range into a full list.
432// Topics: List Handling, Type Conversion
433// See Also: scalar_vec3(), force_list()
434// Usage:
435// list = list(l)
436// Description:
437// Expands a range into a full list. If given a list, returns it verbatim.
438// If given a string, explodes it into a list of single letters.
439// Arguments:
440// l = The value to expand.
441// Example:
442// l1 = list([3:2:9]); // Returns: [3,5,7,9]
443// l2 = list([3,4,5]); // Returns: [3,4,5]
444// l3 = list("Foo"); // Returns: ["F","o","o"]
445// l4 = list(23); // Returns: [23]
446function list(l) = is_list(l)? l : [for (x=l) x];
447
448
449// Function: force_list()
450// Synopsis: Coerces non-list values into a list.
451// Topics: List Handling
452// See Also: scalar_vec3()
453// Usage:
454// list = force_list(value, [n], [fill]);
455// Description:
456// Coerces non-list values into a list. Makes it easy to treat a scalar input
457// consistently as a singleton list, as well as list inputs.
458// - If `value` is a list, then that list is returned verbatim.
459// - If `value` is not a list, and `fill` is not given, then a list of `n` copies of `value` will be returned.
460// - If `value` is not a list, and `fill` is given, then a list `n` items long will be returned where `value` will be the first item, and the rest will contain the value of `fill`.
461// Arguments:
462// value = The value or list to coerce into a list.
463// n = The number of items in the coerced list. Default: 1
464// fill = The value to pad the coerced list with, after the firt value. Default: undef (pad with copies of `value`)
465// Example:
466// x = force_list([3,4,5]); // Returns: [3,4,5]
467// y = force_list(5); // Returns: [5]
468// z = force_list(7, n=3); // Returns: [7,7,7]
469// w = force_list(4, n=3, fill=1); // Returns: [4,1,1]
470function force_list(value, n=1, fill) =
471 is_list(value) ? value :
472 is_undef(fill)? [for (i=[1:1:n]) value] : [value, for (i=[2:1:n]) fill];
473
474
475// Section: List Modification
476
477// Function: reverse()
478// Synopsis: Reverses the elements of a list.
479// Topics: List Handling
480// See Also: select(), list_rotate()
481// Usage:
482// rlist = reverse(list);
483// Description:
484// Reverses a list or string.
485// Arguments:
486// list = The list or string to reverse.
487// Example:
488// reverse([3,4,5,6]); // Returns [6,5,4,3]
489function reverse(list) =
490 assert(is_list(list)||is_string(list), str("Input to reverse must be a list or string. Got: ",list))
491 let (elems = [ for (i = [len(list)-1 : -1 : 0]) list[i] ])
492 is_string(list)? str_join(elems) : elems;
493
494
495// Function: list_rotate()
496// Synopsis: Rotates the ordering of a list.
497// Topics: List Handling
498// See Also: select(), reverse()
499// Usage:
500// rlist = list_rotate(list, [n]);
501// Description:
502// Rotates the contents of a list by `n` positions left, so that list[n] becomes the first entry of the list.
503// If `n` is negative, then the rotation is `abs(n)` positions to the right.
504// If `list` is a string, then a string is returned with the characters rotates within the string.
505// Arguments:
506// list = The list to rotate.
507// n = The number of positions to rotate by. If negative, rotated to the right. Positive rotates to the left. Default: 1
508// Example:
509// l1 = list_rotate([1,2,3,4,5],-2); // Returns: [4,5,1,2,3]
510// l2 = list_rotate([1,2,3,4,5],-1); // Returns: [5,1,2,3,4]
511// l3 = list_rotate([1,2,3,4,5],0); // Returns: [1,2,3,4,5]
512// l4 = list_rotate([1,2,3,4,5],1); // Returns: [2,3,4,5,1]
513// l5 = list_rotate([1,2,3,4,5],2); // Returns: [3,4,5,1,2]
514// l6 = list_rotate([1,2,3,4,5],3); // Returns: [4,5,1,2,3]
515// l7 = list_rotate([1,2,3,4,5],4); // Returns: [5,1,2,3,4]
516// l8 = list_rotate([1,2,3,4,5],5); // Returns: [1,2,3,4,5]
517// l9 = list_rotate([1,2,3,4,5],6); // Returns: [2,3,4,5,1]
518function list_rotate(list,n=1) =
519 assert(is_list(list)||is_string(list), "Invalid list or string.")
520 assert(is_int(n), "The rotation number should be integer")
521 let (
522 ll = len(list),
523 n = ((n % ll) + ll) % ll,
524 elems = [
525 for (i=[n:1:ll-1]) list[i],
526 for (i=[0:1:n-1]) list[i]
527 ]
528 )
529 is_string(list)? str_join(elems) : elems;
530
531
532
533// Function: shuffle()
534// Synopsis: Randomizes the order of a list.
535// Topics: List Handling
536// See Also: sort(), sortidx(), unique(), unique_count()
537// Usage:
538// shuffled = shuffle(list, [seed]);
539// Description:
540// Shuffles the input list into random order.
541// If given a string, shuffles the characters within the string.
542// If you give a numeric seed value then the permutation
543// will be repeatable.
544// Arguments:
545// list = The list to shuffle.
546// seed = Optional random number seed for the shuffling.
547// Example:
548// // Spades Hearts Diamonds Clubs
549// suits = ["\u2660", "\u2661", "\u2662", "\u2663"];
550// ranks = [2,3,4,5,6,7,8,9,10,"J","Q","K","A"];
551// cards = [for (suit=suits, rank=ranks) str(rank,suit)];
552// deck = shuffle(cards);
553function shuffle(list,seed) =
554 assert(is_list(list)||is_string(list), "Invalid input." )
555 is_string(list)? str_join(shuffle([for (x = list) x],seed=seed)) :
556 len(list)<=1 ? list :
557 let(
558 rval = is_num(seed) ? rands(0,1,len(list),seed_value=seed)
559 : rands(0,1,len(list)),
560 left = [for (i=[0:len(list)-1]) if (rval[i]< 0.5) list[i]],
561 right = [for (i=[0:len(list)-1]) if (rval[i]>=0.5) list[i]]
562 )
563 concat(shuffle(left), shuffle(right));
564
565
566
567// Function: repeat_entries()
568// Synopsis: Repeats list entries (as uniformly as possible) to make list of specified length.
569// Topics: List Handling
570// See Also: repeat()
571// Usage:
572// newlist = repeat_entries(list, N, [exact]);
573// Description:
574// Takes a list as input and duplicates some of its entries to produce a list
575// with length `N`. If the requested `N` is not a multiple of the list length then
576// the entries will be duplicated as uniformly as possible. You can also set `N` to a vector,
577// in which case len(N) must equal len(list) and the output repeats the ith entry N[i] times.
578// In either case, the result will be a list of length `N`. The `exact` option requires
579// that the final length is exactly as requested. If you set it to `false` then the
580// algorithm will favor uniformity and the output list may have a different number of
581// entries due to rounding.
582// .
583// When applied to a path the output path is the same geometrical shape but has some vertices
584// repeated. This can be useful when you need to align paths with a different number of points.
585// (See also subdivide_path for a different way to do that.)
586// Arguments:
587// list = list whose entries will be repeated
588// N = scalar total number of points desired or vector requesting N[i] copies of vertex i.
589// exact = if true return exactly the requested number of points, possibly sacrificing uniformity. If false, return uniform points that may not match the number of points requested. Default: True
590// Example:
591// list = [0,1,2,3];
592// a = repeat_entries(list, 6); // Returns: [0,0,1,2,2,3]
593// b = repeat_entries(list, 6, exact=false); // Returns: [0,0,1,1,2,2,3,3]
594// c = repeat_entries(list, [1,1,2,1], exact=false); // Returns: [0,1,2,2,3]
595function repeat_entries(list, N, exact=true) =
596 assert(is_list(list) && len(list)>0, "The list cannot be void.")
597 assert((is_finite(N) && N>0) || is_vector(N,len(list)),
598 "Parameter N must be a number greater than zero or vector with the same length of `list`")
599 let(
600 length = len(list),
601 reps_guess = is_list(N)? N : repeat(N/length,length),
602 reps = exact ?
603 _sum_preserving_round(reps_guess)
604 : [for (val=reps_guess) round(val)]
605 )
606 [for(i=[0:length-1]) each repeat(list[i],reps[i])];
607
608
609// Function: list_pad()
610// Synopsis: Extend list to specified length.
611// Topics: List Handling
612// See Also: force_list(), scalar_vec3()
613// Usage:
614// newlist = list_pad(list, minlen, [fill]);
615// Description:
616// If the list `list` is shorter than `minlen` length, pad it to length with the value given in `fill`.
617// Arguments:
618// list = A list.
619// minlen = The minimum length to pad the list to.
620// fill = The value to pad the list with. Default: `undef`
621// Example:
622// list = [3,4,5];
623// nlist = list_pad(list,5,23); // Returns: [3,4,5,23,23]
624function list_pad(list, minlen, fill) =
625 assert(is_list(list), "Invalid input." )
626 concat(list,repeat(fill,minlen-len(list)));
627
628
629// Function: list_set()
630// Synopsis: Sets the value of specific list items.
631// Topics: List Handling
632// See Also: list_insert(), list_remove(), list_remove_values()
633// Usage:
634// list = list_set(list, indices, values, [dflt], [minlen]);
635// Description:
636// Takes the input list and returns a new list such that `list[indices[i]] = values[i]` for all of
637// the (index,value) pairs supplied and unchanged for other indices. If you supply `indices` that are
638// larger that the length of the list then the list is extended and filled in with the `dflt` value.
639// If you specify indices smaller than zero then they index from the end, with -1 being the last element.
640// Negative indexing does not wrap around: an error occurs if you give a value smaller than `-len(list)`.
641// If you set `minlen` then the list is lengthed, if necessary, by padding with `dflt` to that length.
642// Repetitions in `indices` are not allowed. The lists `indices` and `values` must have the same length.
643// If `indices` is given as a scalar, then that index of the given `list` will be set to the scalar value of `values`.
644// Arguments:
645// list = List to set items in. Default: []
646// indices = List of indices into `list` to set.
647// values = List of values to set.
648// dflt = Default value to store in sparse skipped indices.
649// minlen = Minimum length to expand list to.
650// Example:
651// a = list_set([2,3,4,5], 2, 21); // Returns: [2,3,21,5]
652// b = list_set([2,3,4,5], [1,3], [81,47]); // Returns: [2,81,4,47]
653function list_set(list=[],indices,values,dflt=0,minlen=0) =
654 assert(is_list(list))
655 !is_list(indices)?
656 assert(is_finite(indices))
657 let(
658 index = indices<0 ? indices+len(list) : indices
659 )
660 assert(index>=0, str("Index ",indices," is smaller than negative list length"))
661 (
662 index<len(list) ?
663 [
664 for(i=[0:1:index-1]) list[i],
665 values,
666 for(i=[index+1:1:len(list)-1]) list[i],
667 for(i=[len(list):1:minlen-1]) dflt
668 ]
669 : concat(list, repeat(dflt, index-len(list)), [values], repeat(dflt, minlen-index-1))
670 )
671 : indices==[] && values==[]
672 ? concat(list, repeat(dflt, minlen-len(list)))
673 : assert(is_vector(indices) && is_list(values) && len(values)==len(indices),
674 "Index list and value list must have the same length")
675 let( indices = [for(ind=indices) ind<0 ? ind+len(list) : ind],
676 midx = max(len(list)-1, max(indices))
677 )
678 assert(min(indices)>=0, "Index list contains value smaller than negative list length")
679 [
680 for (i=[0:1:midx])
681 let(
682 j = search(i,indices,0),
683 k = j[0]
684 )
685 assert( len(j)<2, "Repeated indices are not allowed." )
686 k!=undef ? values[k]
687 : i<len(list) ? list[i]
688 : dflt,
689 each repeat(dflt, minlen-max(len(list),max(indices)+1))
690 ];
691
692
693
694// Function: list_insert()
695// Synopsis: Inserts values into the middle of a list.
696// Topics: List Handling
697// See Also: list_set(), list_remove(), list_remove_values()
698// Usage:
699// list = list_insert(list, indices, values);
700// Description:
701// Insert `values` into `list` before position `indices`. The indices for insertion
702// are based on the original list, before any insertions have occurred.
703// You can use negative indices to count from the end of the list. Note that -1 refers
704// to the last element, so the insertion will be *before* the last element.
705// Arguments:
706// list = list to insert items into
707// indices = index or list of indices where values are inserted
708// values = value or list of values to insert
709// Example:
710// a = list_insert([3,6,9,12],1,5); // Returns [3,5,6,9,12]
711// b = list_insert([3,6,9,12],[1,3],[5,11]); // Returns [3,5,6,9,11,12]
712function list_insert(list, indices, values) =
713 assert(is_list(list))
714 !is_list(indices) ?
715 assert(is_finite(indices), "Invalid indices." )
716 let(indices = indices<0 ? indices+len(list) : indices)
717 assert(indices>=0, "Index is too small, must be >= len(list)")
718 assert( indices<=len(list), "Indices must be <= len(list) ." )
719 [
720 for (i=idx(list)) each ( i==indices? [ values, list[i] ] : [ list[i] ] ),
721 if (indices==len(list)) values
722 ] :
723 indices==[] && values==[] ? list :
724 assert( is_vector(indices) && is_list(values) && len(values)==len(indices),
725 "Index list and value list must have the same length")
726 assert( max(indices)<=len(list), "Indices must be <= len(list)." )
727 let(
728 indices = [for(ind=indices) ind<0 ? ind+len(list) : ind],
729 maxidx = max(indices),
730 minidx = min(indices)
731 )
732 assert(minidx>=0, "Index list contains values that are too small")
733 assert(maxidx<=len(list), "Index list contains values that are too large")
734 [
735 for (i=[0:1:minidx-1] ) list[i],
736 for (i=[minidx : min(maxidx, len(list)-1)] )
737 let(
738 j = search(i,indices,0),
739 k = j[0],
740 x = assert( len(j)<2, "Repeated indices are not allowed." )
741 ) each ( k != undef ? [ values[k], list[i] ] : [ list[i] ] ),
742 for ( i = [min(maxidx, len(list)-1)+1 : 1 : len(list)-1] ) list[i],
743 if (maxidx == len(list)) values[max_index(indices)]
744 ];
745
746
747// Function: list_remove()
748// Synopsis: Removes items by index from a list.
749// Topics: List Handling
750// See Also: list_set(), list_insert(), list_remove_values()
751// Usage:
752// list = list_remove(list, ind);
753// Description:
754// If `ind` is a number remove `list[ind]` from the list. If `ind` is a list of indices
755// remove from the list the item all items whose indices appear in `ind`. If you give
756// indices that are not in the list they are ignored.
757// Arguments:
758// list = The list to remove items from.
759// ind = index or list of indices of items to remove.
760// Example:
761// a = list_remove([3,6,9,12],1); // Returns: [3,9,12]
762// b = list_remove([3,6,9,12],[1,3]); // Returns: [3,9]
763// c = list_remove([3,6],3); // Returns: [3,6]
764function list_remove(list, ind) =
765 assert(is_list(list), "Invalid list in list_remove")
766 is_finite(ind) ?
767 (
768 (ind<0 || ind>=len(list)) ? list
769 :
770 [
771 for (i=[0:1:ind-1]) list[i],
772 for (i=[ind+1:1:len(list)-1]) list[i]
773 ]
774 )
775 : ind==[] ? list
776 : assert( is_vector(ind), "Invalid index list in list_remove")
777 let(sres = search(count(list),ind,1))
778 [
779 for(i=idx(list))
780 if (sres[i] == [])
781 list[i]
782 ];
783
784// This method is faster for long lists with few values to remove
785// let( rem = list_set([], indices, repeat(1,len(indices)), minlen=len(list)))
786// [for(i=idx(list)) if (rem[i]==0) list[i]];
787
788
789
790// Function: list_remove_values()
791// Synopsis: Removes items by value from a list.
792// Topics: List Handling
793// See Also: list_set(), list_insert(), list_remove()
794// Usage:
795// list = list_remove_values(list, values, [all]);
796// Description:
797// Removes the first, or all instances of the given value or list of values from the list.
798// If you specify `all=false` and list a value twice then the first two instances will be removed.
799// Note that if you want to remove a list value such as `[3,4]` then you must give it as
800// a singleton list, or it will be interpreted as a list of two scalars to remove.
801// Arguments:
802// list = The list to modify.
803// values = The value or list of values to remove from the list.
804// all = If true, remove all instances of the value `value` from the list `list`. If false, remove only the first. Default: false
805// Example:
806// test = [3,4,[5,6],7,5,[5,6],4,[6,5],7,[4,4]];
807// a=list_remove_values(test,4); // Returns: [3, [5, 6], 7, 5, [5, 6], 4, [6, 5], 7, [4, 4]]
808// b=list_remove_values(test,[4,4]); // Returns: [3, [5, 6], 7, 5, [5, 6], [6, 5], 7, [4, 4]]
809// c=list_remove_values(test,[4,7]); // Returns: [3, [5, 6], 5, [5, 6], 4, [6, 5], 7, [4, 4]]
810// d=list_remove_values(test,[5,6]); // Returns: [3, 4, [5, 6], 7, [5, 6], 4, [6, 5], 7, [4, 4]]
811// e=list_remove_values(test,[[5,6]]); // Returns: [3,4,7,5,[5,6],4,[6,5],7,[4,4]]
812// f=list_remove_values(test,[[5,6]],all=true); // Returns: [3,4,7,5,4,[6,5],7,[4,4]]
813// animals = ["bat", "cat", "rat", "dog", "bat", "rat"];
814// animals2 = list_remove_values(animals, "rat"); // Returns: ["bat","cat","dog","bat","rat"]
815// nonflying = list_remove_values(animals, "bat", all=true); // Returns: ["cat","rat","dog","rat"]
816// animals3 = list_remove_values(animals, ["bat","rat"]); // Returns: ["cat","dog","bat","rat"]
817// domestic = list_remove_values(animals, ["bat","rat"], all=true); // Returns: ["cat","dog"]
818// animals4 = list_remove_values(animals, ["tucan","rat"], all=true); // Returns: ["bat","cat","dog","bat"]
819function list_remove_values(list,values=[],all=false) =
820 !is_list(values)? list_remove_values(list, values=[values], all=all) :
821 assert(is_list(list), "Invalid list")
822 len(values)==0 ? list :
823 len(values)==1 ?
824 (
825 !all ?
826 (
827 let(firsthit = search(values,list,1)[0])
828 firsthit==[] ? list
829 : list[firsthit]==values[0] ? list_remove(list,firsthit)
830 : let(allhits = search(values,list,0)[0],
831 allind = [for(i=allhits) if (list[i]==values[0]) i]
832 )
833 allind==[] ? list : list_remove(list,min(allind))
834 )
835 :
836 (
837 let(allhits = search(values,list,0)[0],
838 allind = [for(i=allhits) if (list[i]==values[0]) i]
839 )
840 allind==[] ? list : list_remove(list,allind)
841 )
842 )
843 :!all ? list_remove_values(list_remove_values(list, values[0],all=all), list_tail(values),all=all)
844 :
845 [
846 for(i=idx(list))
847 let(hit=search([list[i]],values,0)[0])
848 if (hit==[]) list[i]
849 else
850 let(check = [for(j=hit) if (values[j]==list[i]) 1])
851 if (check==[]) list[i]
852 ];
853
854
855
856// Section: List Iteration Index Helper
857
858// Function: idx()
859// Synopsis: Returns a range useful for iterating over a list.
860// Topics: List Handling, Iteration
861// See Also: count()
862// Usage:
863// range = idx(list, [s=], [e=], [step=]);
864// for(i=idx(list, [s=], [e=], [step=])) ...
865// Description:
866// Returns the range that gives the indices for a given list. This makes is a little bit
867// easier to loop over a list by index, when you need the index numbers and looping of list values isn't enough.
868// Note that the return is a **range** not a list.
869// Arguments:
870// list = The list to returns the index range of.
871// ---
872// s = The starting index. Default: 0
873// e = The delta from the end of the list. Default: -1 (end of list)
874// step = The step size to stride through the list. Default: 1
875// Example(2D):
876// colors = ["red", "green", "blue"];
877// for (i=idx(colors)) right(20*i) color(colors[i]) circle(d=10);
878function idx(list, s=0, e=-1, step=1) =
879 assert(is_list(list)||is_string(list), "Invalid input." )
880 let( ll = len(list) )
881 ll == 0 ? [0:1:ll-1] :
882 let(
883 _s = posmod(s,ll),
884 _e = posmod(e,ll)
885 ) [_s : step : _e];
886
887
888// Section: Lists of Subsets
889
890
891// Function: pair()
892// Synopsis: Returns a list of overlapping consecutive pairs in a list.
893// Topics: List Handling, Iteration
894// See Also: idx(), triplet(), combinations(), permutations()
895// Usage:
896// p = pair(list, [wrap]);
897// for (p = pair(list, [wrap])) ... // On each iteration, p contains a list of two adjacent items.
898// Description:
899// Returns a list of all of the pairs of adjacent items from a list, optionally wrapping back to the front. The pairs overlap, and
900// are returned in order starting with the first two entries in the list. If the list has less than two elements, the empty list is returned.
901// Arguments:
902// list = The list to use for making pairs
903// wrap = If true, wrap back to the start from the end. ie: return the last and first items as the last pair. Default: false
904// Example(2D): Does NOT wrap from end to start,
905// for (p = pair(circle(d=40, $fn=12)))
906// stroke(p, endcap2="arrow2");
907// Example(2D): Wraps around from end to start.
908// for (p = pair(circle(d=40, $fn=12), wrap=true))
909// stroke(p, endcap2="arrow2");
910// Example:
911// l = ["A","B","C","D"];
912// echo([for (p=pair(l)) str(p.y,p.x)]); // Outputs: ["BA", "CB", "DC"]
913function pair(list, wrap=false) =
914 assert(is_list(list)||is_string(list), "Invalid input." )
915 assert(is_bool(wrap))
916 let( L = len(list)-1)
917 L<1 ? [] :
918 [
919 for (i=[0:1:L-1]) [list[i], list[i+1]],
920 if(wrap) [list[L], list[0]]
921 ];
922
923
924
925// Function: triplet()
926// Synopsis: Returns a list of overlapping consecutive triplets in a list.
927// Topics: List Handling, Iteration
928// See Also: idx(), pair(), combinations(), permutations()
929// Usage:
930// list = triplet(list, [wrap]);
931// for (t = triplet(list, [wrap])) ...
932// Description:
933// Returns a list of all adjacent triplets from a list, optionally wrapping back to the front.
934// If you set `wrap` to true then the first triplet is the one centered on the first list element, so it includes
935// the last element and the first two elements. If the list has fewer than three elements then the empty list is returned.
936// Arguments:
937// list = list to produce triplets from
938// wrap = if true, wrap triplets around the list. Default: false
939// Example:
940// list = [0,1,2,3,4];
941// a = triplet(list); // Returns [[0,1,2],[1,2,3],[2,3,4]]
942// b = triplet(list,wrap=true); // Returns [[4,0,1],[0,1,2],[1,2,3],[2,3,4],[3,4,0]]
943// letters = ["A","B","C","D","E"];
944// [for (p=triplet(letters)) str(p.z,p.y,p.x)]; // Returns: ["CBA", "DCB", "EDC"]
945// Example(2D):
946// path = [for (i=[0:24]) polar_to_xy(i*2, i*360/12)];
947// for (t = triplet(path)) {
948// a = t[0]; b = t[1]; c = t[2];
949// v = unit(unit(a-b) + unit(c-b));
950// translate(b) rot(from=FWD,to=v) anchor_arrow2d();
951// }
952// stroke(path);
953function triplet(list, wrap=false) =
954 assert(is_list(list)||is_string(list), "Invalid input." )
955 assert(is_bool(wrap))
956 let(L=len(list))
957 L<3 ? [] :
958 [
959 if(wrap) [list[L-1], list[0], list[1]],
960 for (i=[0:1:L-3]) [list[i],list[i+1],list[i+2]],
961 if(wrap) [list[L-2], list[L-1], list[0]]
962 ];
963
964
965// Function: combinations()
966// Synopsis: Returns a list of all combinations of the list entries.
967// Topics: List Handling, Iteration
968// See Also: idx(), pair(), triplet(), permutations()
969// Usage:
970// list = combinations(l, [n]);
971// Description:
972// Returns a list of all of the (unordered) combinations of `n` items out of the given list `l`.
973// For the list `[1,2,3,4]`, with `n=2`, this will return `[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]`.
974// For the list `[1,2,3,4]`, with `n=3`, this will return `[[1,2,3], [1,2,4], [1,3,4], [2,3,4]]`.
975// Arguments:
976// l = The list to provide permutations for.
977// n = The number of items in each combination. Default: 2
978// Example:
979// pairs = combinations([3,4,5,6]); // Returns: [[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]
980// triplets = combinations([3,4,5,6],n=3); // Returns: [[3,4,5],[3,4,6],[3,5,6],[4,5,6]]
981// Example(2D):
982// for (p=combinations(regular_ngon(n=7,d=100))) stroke(p);
983function combinations(l,n=2,_s=0) =
984 assert(is_list(l), "Invalid list." )
985 assert( is_finite(n) && n>=1 && n<=len(l), "Invalid number `n`." )
986 n==1
987 ? [for (i=[_s:1:len(l)-1]) [l[i]]]
988 : [for (i=[_s:1:len(l)-n], p=combinations(l,n=n-1,_s=i+1)) concat([l[i]], p)];
989
990
991
992// Function: permutations()
993// Synopsis: Returns a list of all permutations of the list entries.
994// Topics: List Handling, Iteration
995// See Also: idx(), pair(), triplet(), combinations()
996// Usage:
997// list = permutations(l, [n]);
998// Description:
999// Returns a list of all of the (ordered) permutation `n` items out of the given list `l`.
1000// For the list `[1,2,3]`, with `n=2`, this will return `[[1,2],[1,3],[2,1],[2,3],[3,1],[3,2]]`
1001// For the list `[1,2,3]`, with `n=3`, this will return `[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`
1002// Arguments:
1003// l = The list to provide permutations for.
1004// n = The number of items in each permutation. Default: 2
1005// Example:
1006// pairs = permutations([3,4,5,6]); // // Returns: [[3,4],[3,5],[3,6],[4,3],[4,5],[4,6],[5,3],[5,4],[5,6],[6,3],[6,4],[6,5]]
1007function permutations(l,n=2) =
1008 assert(is_list(l), "Invalid list." )
1009 assert( is_finite(n) && n>=1 && n<=len(l), "Invalid number `n`." )
1010 n==1
1011 ? [for (i=[0:1:len(l)-1]) [l[i]]]
1012 : [for (i=idx(l), p=permutations([for (j=idx(l)) if (i!=j) l[j]], n=n-1)) concat([l[i]], p)];
1013
1014
1015
1016// Section: Changing List Structure
1017
1018
1019// Function: list_to_matrix()
1020// Synopsis: Groups items in a list into sublists.
1021// Topics: Matrices, List Handling
1022// See Also: column(), submatrix(), hstack(), flatten(), full_flatten()
1023// Usage:
1024// groups = list_to_matrix(v, cnt, [dflt]);
1025// Description:
1026// Takes a flat list of values, and groups items in sets of `cnt` length.
1027// The opposite of this is `flatten()`.
1028// Arguments:
1029// v = The list of items to group.
1030// cnt = The number of items to put in each grouping.
1031// dflt = The default value to fill in with if the list is not a multiple of `cnt` items long. Default: undef
1032// Example:
1033// v = [1,2,3,4,5,6];
1034// a = list_to_matrix(v,2) // returns [[1,2], [3,4], [5,6]]
1035// b = list_to_matrix(v,3) // returns [[1,2,3], [4,5,6]]
1036// c = list_to_matrix(v,4,0) // returns [[1,2,3,4], [5,6,0,0]]
1037function list_to_matrix(v, cnt, dflt=undef) =
1038 [for (i = [0:cnt:len(v)-1]) [for (j = [0:1:cnt-1]) default(v[i+j], dflt)]];
1039
1040
1041
1042// Function: flatten()
1043// Synopsis: Flattens a list of sublists into a single list.
1044// Topics: Matrices, List Handling
1045// See Also: column(), submatrix(), hstack(), full_flatten()
1046// Usage:
1047// list = flatten(l);
1048// Description:
1049// Takes a list of lists and flattens it by one level.
1050// Arguments:
1051// l = List to flatten.
1052// Example:
1053// l = flatten([[1,2,3], [4,5,[6,7,8]]]); // returns [1,2,3,4,5,[6,7,8]]
1054function flatten(l) =
1055 !is_list(l)? l :
1056 [for (a=l) if (is_list(a)) (each a) else a];
1057
1058
1059// Function: full_flatten()
1060// Synopsis: Recursively flattens nested sublists into a single list of non-list values.
1061// Topics: Matrices, List Handling
1062// See Also: column(), submatrix(), hstack(), flatten()
1063// Usage:
1064// list = full_flatten(l);
1065// Description:
1066// Collects in a list all elements recursively found in any level of the given list.
1067// The output list is ordered in depth first order.
1068// Arguments:
1069// l = List to flatten.
1070// Example:
1071// l = full_flatten([[1,2,3], [4,5,[6,7,8]]]); // returns [1,2,3,4,5,6,7,8]
1072function full_flatten(l) =
1073 !is_list(l)? l :
1074 [for (a=l) if (is_list(a)) (each full_flatten(a)) else a];
1075
1076
1077
1078// Section: Set Manipulation
1079
1080// Function: set_union()
1081// Synopsis: Merges two lists, returning a list of unique items.
1082// Topics: Set Handling, List Handling
1083// See Also: set_difference(), set_intersection()
1084// Usage:
1085// s = set_union(a, b, [get_indices]);
1086// Description:
1087// Given two sets (lists with unique items), returns the set of unique items that are in either `a` or `b`.
1088// If `get_indices` is true, a list of indices into the new union set are returned for each item in `b`,
1089// in addition to returning the new union set. In this case, a 2-item list is returned, `[INDICES, NEWSET]`,
1090// where INDICES is the list of indices for items in `b`, and NEWSET is the new union set.
1091// Arguments:
1092// a = One of the two sets to merge.
1093// b = The other of the two sets to merge.
1094// get_indices = If true, indices into the new union set are also returned for each item in `b`. Returns `[INDICES, NEWSET]`. Default: false
1095// Example:
1096// set_a = [2,3,5,7,11];
1097// set_b = [1,2,3,5,8];
1098// set_u = set_union(set_a, set_b);
1099// // set_u now equals [2,3,5,7,11,1,8]
1100// set_v = set_union(set_a, set_b, get_indices=true);
1101// // set_v now equals [[5,0,1,2,6], [2,3,5,7,11,1,8]]
1102function set_union(a, b, get_indices=false) =
1103 assert( is_list(a) && is_list(b), "Invalid sets." )
1104 let(
1105 found1 = search(b, a),
1106 found2 = search(b, b),
1107 c = [ for (i=idx(b))
1108 if (found1[i] == [] && found2[i] == i)
1109 b[i]
1110 ],
1111 nset = concat(a, c)
1112 )
1113 ! get_indices ? nset :
1114 let(
1115 la = len(a),
1116 found3 = search(b, c),
1117 idxs = [ for (i=idx(b))
1118 (found1[i] != [])? found1[i] : la + found3[i]
1119 ]
1120 ) [idxs, nset];
1121
1122
1123// Function: set_difference()
1124// Synopsis: Returns a list of unique items that are in list A, but not in list B.
1125// Topics: Set Handling, List Handling
1126// See Also: set_union(), set_intersection()
1127// Usage:
1128// s = set_difference(a, b);
1129// Description:
1130// Given two sets (lists with unique items), returns the set of items that are in `a`, but not `b`.
1131// Arguments:
1132// a = The starting set.
1133// b = The set of items to remove from set `a`.
1134// Example:
1135// set_a = [2,3,5,7,11];
1136// set_b = [1,2,3,5,8];
1137// set_d = set_difference(set_a, set_b);
1138// // set_d now equals [7,11]
1139function set_difference(a, b) =
1140 assert( is_list(a) && is_list(b), "Invalid sets." )
1141 let( found = search(a, b, num_returns_per_match=1) )
1142 [ for (i=idx(a)) if(found[i]==[]) a[i] ];
1143
1144
1145// Function: set_intersection()
1146// Synopsis: Returns a list of unique items that are in both given lists.
1147// Topics: Set Handling, List Handling
1148// See Also: set_union(), set_difference()
1149// Usage:
1150// s = set_intersection(a, b);
1151// Description:
1152// Given two sets (lists with unique items), returns the set of items that are in both sets.
1153// Arguments:
1154// a = The starting set.
1155// b = The set of items to intersect with set `a`.
1156// Example:
1157// set_a = [2,3,5,7,11];
1158// set_b = [1,2,3,5,8];
1159// set_i = set_intersection(set_a, set_b);
1160// // set_i now equals [2,3,5]
1161function set_intersection(a, b) =
1162 assert( is_list(a) && is_list(b), "Invalid sets." )
1163 let( found = search(a, b, num_returns_per_match=1) )
1164 [ for (i=idx(a)) if(found[i]!=[]) a[i] ];
1165
1166
1167
1168
1169// vim: expandtab tabstop=4 shiftwidth=4 softtabstop=4 nowrap